package com.github.hgkmail.hello.leetcode101.unionfind;

import com.github.hgkmail.hello.leetcode101.base.UF;

import java.util.Arrays;

public class LC684RedundantConnection {
    public int[] findRedundantConnection(int[][] edges) {
        int n=edges.length;
        if (n<=0) {
            //找不到，返回-1，-1
            return new int[]{-1, -1};
        }
        //用UF判断是否有环
        UF uf = new UF(n+1);
        for (int i = 0; i < n; i++) {
            int[] e = edges[i];
            //未加入UF前，判断是否已经相连
            if (uf.isConnected(e[0], e[1])) {
                return e;
            }
            //把边加入UF
            uf.union(e[0], e[1]);
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] e = new LC684RedundantConnection().findRedundantConnection(new int[][]{
                {1,2}, {1,3}, {2,3}
        });
        System.out.println(Arrays.toString(e));
    }
}
